package com.zhupf.stack;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author zhupf
 * @date 2024年02月22日 9:52
 * @Description   again
 *
 *  84. 柱状图中最大的矩形
 *  给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 *
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 *
 */
public class LargestRectangleArea {

    public static void main(String[] args) {
        int[] heights = {3,2,1,2,3};
        System.out.println(largestRectangleArea2(heights));

    }

    public static int largestRectangleArea2(int[] heights) {
        int ans= 0;
        int len = heights.length;
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < heights.length; i++) {
            int cur = heights[i];
            while(!deque.isEmpty() && cur <= heights[deque.peek()]){
                Integer pop = deque.pop();
                ans = Math.max((i-pop)*heights[pop]+((deque.isEmpty()?pop:(pop-deque.peek()-1))*heights[pop]),ans);
            }
            deque.push(i);
        }
        while(!deque.isEmpty()){
            Integer pop = deque.pop();
            ans = Math.max((len-pop)*heights[pop]+((deque.isEmpty()?pop:(pop-deque.peek()-1))*heights[pop]),ans);
        }
        return ans;
    }


    public static int largestRectangleArea(int[] heights) {
        Deque<Integer> stk = new LinkedList<>();
        int idx = 0;
        int ans = 0;
        while (idx < heights.length){
            if(!stk.isEmpty() && heights[idx] < heights[stk.peek()]){
                int cur = heights[idx];
                while (!stk.isEmpty() && cur < heights[stk.peek()]){
                    Integer pop = stk.pop();
                    int right = (idx - pop) * heights[pop];
                    int left = stk.isEmpty()? (pop)*heights[pop] : (pop-stk.peek()-1)*heights[pop];
                    ans = Math.max((right + left), ans);
                }
            }
            stk.push(idx);
            idx++;
        }
        while (!stk.isEmpty()){
            Integer pop = stk.pop();
            int right = (heights.length-pop)*heights[pop];
            int left = stk.isEmpty()? (pop)*heights[pop] : (pop-stk.peek()-1)*heights[pop];
            ans= Math.max((right+left),ans);
        }
        return ans;
    }
}
